import Foundation

public class ArrayQueue {
    private var items: [String]!
    private var n: Int = 0
    private var head: Int = 0
    private var tail: Int = 0
    
    //申请一个指定大小的队列
    init(_ capacity: Int) {
        self.n = capacity
        self.items = [String]()
    }
    
    //入列
    func enqueue(_ item: String) -> Bool {
        //如果队列已满
        if tail == n {
            return false
        }
        items[tail] = item
        //更新队尾
        tail += 1
        return true
    }
    
    /*
     出列
     
     当队列末尾没有空间时,检测是否队列已满
     如果未满,进行数据搬迁,搬迁后在进行入列操作
     */
    func dequeue() -> String? {
        //如果队列末尾没有空间
        if tail == n {
            //整个队列都满了
            if head == 0 {
                return nil
            }
            //数据搬迁
            for i in head..<tail {
                items[i - head] = items[i]
            }
        }
        let item = items[head]
        //更新队头
        head += 1
        return item
    }
}


/* 循环队列
 可以避免队列到尾后, 需要进行数据搬迁工作
 判空: head == tail
 判满: (tail + 1)%n = head
 */
public class CircularQueue {
    private var items: [String]!
    private var n: Int = 0
    private var head: Int = 0
    private var tail: Int = 0
    
    init(_ capacity: Int) {
        items = [String]()
        n = capacity
    }
    
    func enqueue(_ item: String) -> Bool {
        //如果队列满了
        if (tail + 1)%n == head {
            return false
        }
        items[tail] = item
        tail = (tail + 1)%n
        return true
    }
    
    func dequeue() -> String? {
        if tail == head {
            return nil
        }
        let item = items[head]
        head = (head + 1)%n
        return item
    }
}
